Different techniques have been used for increasing cache locality for various workloads. One of the oldest and most basic algorithms is LRU (least recently used) which evicts the page from the cache that was not accessed the longest. LRU is currently the policy of choice in many database systems due to its small overhead and tuning-free operation. Many variants of LRU have been used since. Examples are LRU-K [E. J. O'Neil, P. E. O'Neil, and G. Weikum, “The LRU-K Page Replacement Algorithm For Database Disk Buffering,” Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 297-306, 1993] (which evicts the page whose Kth most recent access is the longest in the past), 2Q [T. Johnson and D. Shasha, “2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm,” Proc. Int. Conf. on Very Large Data Bases, pages 439-450, 1994] (which reduces LRU-K's logarithmic overhead to a constant overhead), LFU [J. Robinson and M. Devarakonda, “Data Cache Management Using Frequency-Based Replacement,” Proc. ACM SIGMETRICS Conf., pages 134-142, 1990] (which evicts the page that was accessed least frequently), and hybrids such as LRFU [D. Lee, J. Choi, J.-H. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S. Kim, LRFU: A Spectrum Of Policies That Subsumes The Least Recently Used And Least Frequently Used Policies, IEEE Trans. Computers, 50(12):1352-1360, 2001] (combining LRU and LFU) and ARC [N. Megiddo and D. Modha, “Outperforming LRU With An Adaptive Replacement Cache,” 2004] (which can adaptively switch between different eviction policies). [L. Belady, “A study of replacement algorithms for virtual storage computers” IBM Systems Journal, 5(2):78-101, 1966] gave an optimal offline algorithm, MIN, for the cache replacement problem which evicts the page that is accessed the farthest in the future. All these techniques (1) assume the workload consists of requests for specific pages and (2) are very general (i.e., work for any such workload).
There are systems that exploit knowledge about the workload to improve caching. [e.g., G. M. Sacco and M. Schkolnick, “A Mechanism For Managing The Buffer Pool In A Relational Database System Using The Hot Set Model,” Proc. Int. Conf. on Very Large Data Bases, pages 257-262, 1982] use this knowledge to derive the “hot set” of pages during query execution. This can then be used to schedule queries in a smart way to prevent unnecessary page swapping. Chou and DeWitt [H. Chou and D. DeWitt, “An Evaluation Of Buffer Management Strategies For Relational Database Systems,” Proc. Int. Conf. on Very Large Data Bases, pages 127-141, 1985] improve upon this technique by using multiple page buffers, each with its own eviction policy based on the type of access (table scan, index access, etc). Both of these techniques can reduce the amount of cache misses.
Commercial database vendors such as Red Brick [P. M. Fernandez, “Red brick warehouse: a read-mostly RDBMS for open SMP platforms,” Proc. ACM SIGMOD Int. Conf. on Management of Data, page 492, 1994] and Teradata [T. Walter, “Explaining cache—NCR CTO Todd Walter answers your trickiest questions on Teradata's caching functionality”] employ proprietary algorithms to let the database synchronize multiple table scan operations in order to maximize buffer locality. This idea was taken even further by Harizopoulos et al. [S. Harizopoulos, V. Shkapenyuk, and A. Ailamaki. QPipe, “A simultaneously pipelined relational query engine,” Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 383-394, 2005]. They propose interesting ideas for a new database architecture that tries to maximize reuse of partial query results from the query down to the page access level. This is achieved by detecting overlaps in active query plan operators at query execution time and then exploiting it by pipelining one operator's results to all dependent operators where possible. Two of the operators discussed in that paper are the table and index scan operators. For these, the authors propose to use one scan thread that keeps scanning all pages while table scan operators can attach to and detach from this thread in order to share the scanned pages.
While this approach works well for scans with similar speeds, in practice scan speeds can vary by large margins and even single scans' speeds are usually far from constant due to changes in predicate evaluation overhead. Therefore, the benefit can be lower as scans may start drifting apart.
In addition to cache or page buffer algorithm improvements, other methods to reduce disk access costs for multiple concurrent queries with overlapping data accesses have been investigated. These methods include multi-query optimization [P. Roy, S. Seshadri, S. Sudarshan, and S. Bhobe. Efficient and extensible algorithms for multi query optimization. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 249-260, 2000] (which requires all queries to be known in advance) and query result caching [J. Shim, P. Scheuermann, and R. Vingralek. Dynamic caching of query results for decision support systems. In Proc. Int. Conf. on Scientific and Statistical Database Management, pages 254-263, 1999]. Due to being at a high level of the query execution hierarchy, the latter may miss out on sharing potential for queries that have very different predicates but still end up performing table scans on the same table, for example.
In summary, existing approaches for reducing disk accesses during the execution of multiple queries are either not dynamic enough, or are limiting themselves by enforcing certain access orders or not making full use of the knowledge about the workload.